// Copyright (c) 2012 Christian Kollross / Michael Freymueller

package de.pixel83.piecemaster.ai;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

import de.pixel83.piecemaster.Board;
import de.pixel83.piecemaster.Move;

/**
 * <pre>
 * Acknowledgments to:
 * -Charles Darwin
 * 		for discovering the base principle of this Java class.
 * 
 * - Richard Dawkins
 * 		for his neat explanation of evolution at the example of a genetic algorithm:
 * 		http://www.youtube.com/watch?v=QdtYRJqNe9I
 * </pre>
 */
public class GeneticTrainer {

	private GeneticAi initialAi = null;

	private HashMap<Ai, Integer> population = new HashMap<Ai, Integer>();

	/**
	 * Creates a GeneticTrainer based on MasterAi and a default DNA.
	 */
	private GeneticTrainer() {
		// Converged DNA after first genetic run, depth 3
		// bishop=425;queen=1020;rook=642;king=12563;pawn=158;knight=202

		DNA defaultDNA = new DNA(
				"bishop=425;queen=1020;rook=642;king=12563;pawn=158;knight=202;pawn-increase=50");

		// MasterDNA defaultDNA = new MasterDNA(100, 300, 350, 500, 1000,
		// 10000);
		init(new MasterAiMichi(), defaultDNA);
	}

	public GeneticTrainer(GeneticAi initialAi, DNA initialDNA) {
		init(initialAi, initialDNA);
	}

	private void init(GeneticAi initialAi, DNA dna) {
		this.initialAi = initialAi;
		// Create 10 initial individuals
		for (int i = 0; i < 10; i++) {
			DNA tempDNA = new DNA(dna.toString());
			tempDNA.mutate(50);
			Ai ai = initialAi.generateAi(tempDNA);
			population.put(ai, 0);
		}
	}

	public void run(int gamesPerGenerationAndAi) {
		while (true) {
			// Play each Ai against 2 opponents
			for (Ai ai : population.keySet()) {
				for (int i = 0; i < gamesPerGenerationAndAi; i++) {
					Ai opponent = getRandomAiExcept(ai);
					Ai winner = runGame(ai, opponent);
					if (winner == null) {
						System.out.println("DRAW");
					} else {
						// System.out.println("Winning DNA: "
						// + ((GeneticAi) winner).getDNA().toString());
					}

					// Add up points (+3 for wins, +1 for draw)
					if (winner == null) {
						population.put(ai, population.get(ai) + 1);
						population.put(opponent, population.get(opponent) + 1);
					} else if (winner == ai) {
						Integer oldVal = population.get(ai);
						population.put(ai, oldVal + 3);
					} else if (winner == opponent) {
						Integer oldVal = population.get(opponent);
						population.put(opponent, oldVal + 3);
					}
				}
			}

			// Select 5 winning individuals
			HashMap<Ai, Integer> parentPolupation = new HashMap<Ai, Integer>();
			Map<Ai, Integer> sortedPopulation = sortByValues(population);
			Object[] arr = sortedPopulation.entrySet().toArray();
			for (int i = 0; i < 5; i++) {
				Map.Entry<GeneticAi, Integer> entry = (Entry<GeneticAi, Integer>) arr[i];
				System.out.println("#### Picking Ai with " + entry.getValue()
						+ " points and DNA "
						+ entry.getKey().getDNA().toString());
				parentPolupation.put(entry.getKey(), entry.getValue());
			}

			// Recombination between all individuals AKA group sex and mutation
			// by max 10%
			population = new HashMap<Ai, Integer>();
			Object[] winners = parentPolupation.keySet().toArray();
			for (int i = 0; i < winners.length; i++) {
				for (int n = i + 1; n < winners.length; n++) {
					DNA dna1 = ((GeneticAi) winners[i]).getDNA();
					DNA dna2 = ((GeneticAi) winners[n]).getDNA();
					DNA childDna = dna1.recombine(dna2);
					childDna.mutate(10); // Mutation
					GeneticAi childAi = initialAi.generateAi(childDna);
					population.put(childAi, 0);
				}
			}
			assert (population.size() == 10);
			System.out.println("################## TNG - The Next Generation");
		}
	}

	/**
	 * Play a game of MiniChess between the given AIs.
	 * 
	 * @param ai1
	 * @param ai2
	 * @return
	 */
	private static Ai runGame(Ai ai1, Ai ai2) {
		Board board = new Board();
		Move move = null;
		Board.MoveResult result = Board.MoveResult.OK;

		if (Math.random() > .5) {
			Ai temp = ai1;
			ai1 = ai2;
			ai2 = temp;
		}

		Ai ai = ai1;
		char color = 'W';
		while (result == Board.MoveResult.OK) {
			System.out.println("Drawing: " + board.getColor() + " "
					+ board.getMoveNum());
			move = ai.draw(board, color);
			result = board.move(move);
			//System.out.println("\n#####\n" + board.toString() + "#####\n");
			// Switch to opponent ai and color
			ai = (ai == ai1 ? ai2 : ai1);
			color = Board.invertColor(color);
		}
		if (result == Board.MoveResult.DRAW)
			return null;
		if (result == Board.MoveResult.WIN_W)
			return ai1;
		if (result == Board.MoveResult.WIN_B)
			return ai2;
		return null;
	}

	/**
	 * Picks a random Ai from the population but ignores the given Ai.
	 * 
	 * @param ai
	 * @return
	 */
	private Ai getRandomAiExcept(Ai ai) {
		Ai pick = null;
		Object[] arr = population.entrySet().toArray();
		while (pick == null) {
			double rand = Math.random();
			int id = (int) Math.floor(rand * population.size());
			Ai temp = ((Map.Entry<Ai, Integer>) arr[id]).getKey();
			if (temp != ai)
				pick = temp;
		}
		return pick;
	}

	/**
	 * Helper function to sort the HashMap. Taken from
	 * http://stackoverflow.com/questions
	 * /109383/how-to-sort-a-mapkey-value-on-the-values-in-java
	 * 
	 * @param map
	 * @return
	 */
	public static <K, V extends Comparable<V>> Map<K, V> sortByValues(
			final Map<K, V> map) {
		Comparator<K> valueComparator = new Comparator<K>() {
			public int compare(K k1, K k2) {
				int compare = map.get(k2).compareTo(map.get(k1));
				if (compare == 0)
					return 1;
				else
					return compare;
			}
		};
		Map<K, V> sortedByValues = new TreeMap<K, V>(valueComparator);
		sortedByValues.putAll(map);
		return sortedByValues;
	}

	/**
	 * Starts the training program. Should only print out each generation's
	 * winning DNAs in "productive" stage.
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		DNA dna = new DNA(
				"bishop=425;queen=1020;rook=642;king=12563;pawn=158;knight=202;pawn-increase=50");
		GeneticTrainer trainer = new GeneticTrainer(
				(GeneticAi) new MasterAi2(), dna);
		trainer.run(2);
	}
}